package com.gitee.feizns.explore.data_structure.array.middle;

import java.util.Arrays;
import java.util.Comparator;

/**
 * 合并区间
 * 以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
 * @author feizns
 * @since 2023/9/6
 */
public class Merge {

    /**
     * @param args {@link String[]}
     */
    public static void main(String[] args) {
        //[[2,3],[4,5],[6,7],[8,9],[1,10]]
        int[][] merge = merge(new int[][]{{2, 3},{4, 5}, {6, 7}, {8, 9}, {1, 10}});
        Arrays.stream(merge).map(Arrays::toString).forEach(System.out::println);
//        System.out.println(Arrays.toString(merge));
    }

    /**
     * @param intervals {@link int[][]}
     * @return {@link int[][]}
     */
    public static int[][] merge(int[][] intervals) {
        java.util.Stack<int[]> result = new java.util.Stack<>();
        if ( intervals.length > 0 ) {
            Arrays.sort(intervals, Comparator.comparingInt(o -> o[0]));
            result.push(intervals[0]);
            for (int i = 1; i < intervals.length; i++) {
                if ( same(result.peek(), intervals[i]) )
                    result.push(merge(result.pop(), intervals[i]));
                else
                    result.push(intervals[i]);
            }
        }
        return result.toArray(int[][]::new);
    }

    /**
     * 两个区间有重合
     * @param a {@link int[]}
     * @param b {@link int[]}
     * @return boolean
     */
    public static boolean same(int[] a, int[] b) {
        return !(a[1] < b[0] || b[1] < a[0]);
    }

    /**
     * 合并两个区间
     * @param a {@link int[]}
     * @param b {@link int[]}
     * @return boolean
     */
    public static int[] merge(int[] a, int[] b) {
        return new int[]{ Math.min(a[0], b[0]), Math.max(a[1], b[1]) };
    }

}
